package recursion;

/**
 * @ClassName: leetcode recursion.FibDemo3
 * @Description: TODO
 * @Author: 逸伦
 * @Date: 2022/5/22 16:45
 * @Version: 1.0
 */
public class FibDemo3 {



  public static void main(String[] args) {
    System.out.println(fib(10000));
    System.out.println(fib(10000));
  }

  private static int fib(int n) {
    int[] arr = new int[n + 1];
    arr[1] = arr[2] = 1;
    for (int i = 3; i <= n; i++) {
      arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n];
  }

  private static int fib2(int n) {
    int first = 1;
    int second = 1;
    for (int i = 3; i <= n; i++) {
        second = first + second;
        first = second - first;
    }
    return second;
  }
}
